package leetCode;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 12
 * 贪心算法/停顿循环
 罗马数字包含以下七种字符：I，V，X，L，C，D和M。

 字符          数值
 I             1
 V             5
 X             10
 L             50
 C             100
 D             500
 M             1000
 例如， 罗马数字 2 写做II，即为两个并列的 1。12 写做XII，即为X+II。 27 写做XXVII, 即为XX+V+II。

 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做IIII，而是IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

 I可以放在V(5) 和X(10) 的左边，来表示 4 和 9。
 X可以放在L(50) 和C(100) 的左边，来表示 40 和90。
 C可以放在D(500) 和M(1000) 的左边，来表示400 和900。
 给你一个整数，将其转为罗马数字。

 示例1:
 输入:num = 3
 输出: "III"

 示例2:
 输入:num = 4
 输出: "IV"

 示例3:
 输入:num = 9
 输出: "IX"

 示例4:
 输入:num = 58
 输出: "LVIII"
 解释: L = 50, V = 5, III = 3.

 示例5:
 输入:num = 1994
 输出: "MCMXCIV"
 解释: M = 1000, CM = 900, XC = 90, IV = 4.

 提示：
 1 <= num <= 3999
 */
public class IntegerToRoman {
    public static void main(String[] args) {
        System.out.println(intToRomanMe2(1994));
    }

    static String result = "";
    static Map<Integer, String> itr = Conver();

    //回调实现，很慢
    public static String intToRomanMe(int num) {
        boolean flag = false;
        for (Integer roman_num:itr.keySet()) {
            if ((num - roman_num) > 0){
                num = num - roman_num;
                result += itr.get(roman_num);
                break;
            } else if ((num - roman_num) == 0){
//                num = num - roman_num;
                result += itr.get(roman_num);
                flag = true;
                break;
            }
        }
        if (!flag) {
            intToRomanMe(num);
        }
        return result;
    }

    //while实现，依然很慢，但是StringBuilder比String拼接要快
    public static String intToRomanMe2(int num) {
        StringBuilder result = new StringBuilder();
        Map<Integer, String> itr = Conver();
        for (Integer roman_num:itr.keySet()) {
            while (num >= roman_num) {
                num -= roman_num;
                result.append(itr.get(roman_num));
            }
            if (num == 0) {
                break;
            }
        }
        return result.toString();
    }

    //标准答案，使用数组而不是map，快了三倍！！！使用StringBuilder而不是String，又快了两倍！！100/67
    static int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    static String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    public static String intToRoman(int num) {
        StringBuilder result = new StringBuilder();
        for (int i =0;i < values.length;i++) {
            while (num >= values[i]) {
                num -= values[i];
                result.append(symbols[i]);
            }
            if (num == 0) {
                break;
            }
        }
        return result.toString();
    }

    public static Map<Integer, String> Conver() {
        Map<Integer,String> itr = new LinkedHashMap<>();
        itr.put(1000,"M");
        itr.put(900,"CM");
        itr.put(500,"D");
        itr.put(400,"CD");
        itr.put(100,"C");
        itr.put(90,"XC");
        itr.put(50,"L");
        itr.put(40,"XL");
        itr.put(10,"X");
        itr.put(9,"IX");
        itr.put(5,"V");
        itr.put(4,"IV");
        itr.put(1,"I");
        return itr;
    }
   }
